package top.drose;

import java.util.ArrayDeque;
import java.util.Scanner;

//https://www.luogu.com.cn/problem/P1886
public class p12_1 {


    public static void main(String[] args) {
        //滑动窗口成立的条件就是“首元素是否在窗口内”，这个条件是已知的(由我们自己维护)
        //对于这道题最开始想到的肯定是在deque里面存储a中的元素，但是如此以来，就很难判断
        //元素是否在窗口内了，所以可以在deque里面存储元素在a中的下标
        var N=1000005;
        int[] a=new int[N];
        ArrayDeque<Integer> q=new ArrayDeque<>();

        int n,m;//总长度和窗口长度
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt();
        for(int i=0;i<n;i++){//读入这个序列
            a[i]=sc.nextInt();
        }

        for(int i=0;i<n;i++){
            while((!q.isEmpty())  &&  (a[q.getLast()]>a[i])){
                q.removeLast();//去尾
            }
            q.addLast(i);//插入的时候也是插入下标
            if(i>=(m-1)){//只有窗口里面有三个元素的时候才输出
                while(  ( !q.isEmpty() ) && (  q.getFirst()  <=  (i-m)  )){
                    q.removeFirst();//删头
                }
                System.out.printf("%d ",a[q.getFirst()]);
            }
        }


        /// 上面的输出滑动窗口最小值，下面输出最大值
        System.out.println();q.clear();
        for(int i=0;i<n;i++){
            while((!q.isEmpty()) &&  (a[q.getLast()]<a[i])){
                q.removeLast();
            }
            q.addLast(i);
            if(i>=(m-1)){
                while( ( !q.isEmpty() ) && (  q.getFirst()  <=  (i-m)  )){
                    q.removeFirst();
                }
                System.out.printf("%d ",a[q.getFirst()]);
            }
        }
    }
}
